package com.lw.leetcode.str.a;

/**
 * Created with IntelliJ IDEA.
 *28. 实现 strStr()
 * @author liw
 * @version 1.0
 * @date 2021/8/27 13:29
 */
public class StrStr {

    public static void main(String[] args) {
        StrStr test = new StrStr();

        String[] as = {"", "a", "hello", "aaaaa", "", "bacbababadababacambabacaddababacasdsd", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"};
        String[] bs = {"a", "", "ll", "bba", "", "ababaca", "aaaaaaaaaaaaab"};
//        int[] arr = {-1, 0, 2, -1, 0, 10};

        for (int i = 6; i < as.length; i++) {
            int index = test.strStr(as[i], bs[i]);
//            if (index != arr[i]) {
                System.out.println(as[i] + "   " + as[i].length() );
                System.out.println(bs[i] + "   " + bs[i].length());
//            }
        }
        System.out.println("OK");
    }


    public int strStr(String haystack, String needle) {

        int m = haystack.length();
        int n = needle.length();
        if (n == 0) {
            return 0;
        }
        if (m == 0) {
            return -1;
        }
        char[] c1 = haystack.toCharArray();
        char[] c2 = needle.toCharArray();
        int i = 0;
        int j = 0;
        int[] kmpNext = getKmpNext(c2);
        int t = 0;
        while (i < m && j < n) {
            t++;
            if (j == -1 || c1[i] == c2[j]) {
                i++;
                j++;
            } else {
                j = kmpNext[j];
            }
        }
        System.out.println("比较次数： " + t);
        if (j == n) {
            return i - j;
        } else {
            return -1;
        }
    }

    private int[] getKmpNext(char[] c2) {
        int length = c2.length;
        int[] next = new int[length];
        next[0] = -1;
        int i = 0;
        int j = -1;
        int t = 0;
        while (i < length - 1) {
            t++;
            if (j == -1 || c2[i] == c2[j]) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        System.out.println("预处理次数： " + t);
        return next;
    }

}
